package Ep06_BinaryTree.BT19_0654;

import Ep06_BinaryTree.TreeNode;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/6/1 14:59
 * 说明：lc 0654 优化解法：
 *          区别于lc_0105和lc_0106，本题只有一个数组，不需要进行两个数组间的rootIndex映射
 *          因此舍弃了map，直接在递归方法的for之内比较，再取index和val，不需要再for存入map
 */

public class Best {
    public TreeNode constructMaximumBinaryTree(int[] nums) {

        return traversal(nums, 0, nums.length);
    }

    // 递归方法
    private TreeNode traversal (int[] nums, int begin, int end) {
        if (begin >= end) return null;
        if (end - begin == 1) return new TreeNode(nums[begin]);
        int maxIndex = begin;
        int maxVal = nums[maxIndex];
        for (int i = begin + 1; i < end; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        root.left = traversal(nums, begin, maxIndex);
        root. right = traversal(nums, maxIndex + 1, end);

        return root;
    }
}
